#include <queue>
#include <map>
#include <cstring>
#include <stack>

using namespace std;

class MyStack {
public:
    std::queue<int> _q;

    MyStack() {

    }

    void push(int x) {
        _q.push(x);
    }

    int pop() {
        int n = _q.size() - 1;
        while(n > 0) {
            _q.push(_q.front());
            _q.pop();
            n--;
        }
        int res = _q.front();
        _q.pop();
        return res;
    }

    int top() {
        return _q.back();
    }

    bool empty() {
        return _q.empty();
    }
};

//! 20. 有效的括号
bool isValid(string s) {
    std::stack<char> st;
    for (int i = 0; i < s.size(); i++) {
        if(s[i] == '(' or s[i] == '[' or s[i] == '{') {
            st.push(s[i]);
        } else if(s[i] == ')') {
            if(st.empty() || st.top() != '(') {
                return false;
            } else {
                st.pop();
                continue;
            }
        }else if(s[i] == ']') {
            if(st.empty() || st.top() != '[') {
                return false;
            } else {
                st.pop();
                continue;
            }
        }else if(s[i] == '}') {
            if(st.empty() || st.top() != '{') {
                return false;
            } else {
                st.pop();
                continue;
            }
        } else {
            continue;
        }
    }
    if(st.empty()) {
        return true;
    } else {
        return false;
    }
}

//! 1047. 删除字符串中的所有相邻重复项
string removeDuplicates(string s) {
    string res{s[0]};
    for(int i=1;i<s.size();i++) {
        if(res.empty() || s[i] != res.back()) {
            res.push_back(s[i]);
        } else {
            res.pop_back();
        }
    }
    return res;
}

//! 150. 逆波兰表达式求值
int evalRPN(vector<string> tokens) {
    stack<int> nums;
    for(int i=0;i<tokens.size();i++) {
        if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") {
            nums.push(stoi(tokens[i]));
        } else {
            int num2 = nums.top();
            nums.pop();
            int num1 = nums.top();
            nums.pop();
            if(tokens[i] == "+") {
                nums.push(num1 + num2);
            }else if(tokens[i] == "-") {
                nums.push(num1 - num2);
            }else if(tokens[i] == "*") {
                nums.push(num1 * num2);
            }else if(tokens[i] == "/") {
                nums.push(num1 / num2);
            }
        }
    }
    return nums.top();
}

//! 滑动窗口最大值
vector<int> maxSlidingWindow(vector<int> nums, int k) {
    std::deque<int> window;
    std::vector<int> res;
    window.push_back(nums[0]);
    for(int i=1; i<k; i++) {
        if(!window.empty() && nums[i] <= window.back()) {
            window.push_back(nums[i]);
        } else {
            while(!window.empty() && window.back() < nums[i]) {
                window.pop_back();
            }
            window.push_back(nums[i]);
        }
    }
    res.push_back(window.front());
    for(int i=k; i<nums.size(); i++) {
        // 将超出窗口范围的最大值移出
        if(window.front() == nums[i - k]) {
            window.pop_front();
        }
        if(!window.empty() && nums[i] <= window.back()) {
            window.push_back(nums[i]);
            if(window.size() > k) {
                window.pop_front();
            }
        } else {
            while(!window.empty() && window.back() < nums[i]) {
                window.pop_back();
            }
            window.push_back(nums[i]);
        }
        res.push_back(window.front());
    }

    return res;
}

//! 347. 前 K 个高频元素
vector<int> topKFrequent(vector<int>& nums, int k) {
    std::map<int, int> num2freq;
    std::priority_queue<int, std::vector<int>, std::greater<int>> q;
    for (auto num : nums) {
        num2freq[num]++;
    }
    std::vector<int> res;
    for (auto elem : num2freq) {
        q.push(elem.second);
        if(q.size() > k) {
            q.pop();
        }
    }
    while(!q.empty()) {
        int num = q.top();
        q.pop();
        for (auto elem : num2freq) {
            if (elem.second == num) {
                res.push_back(elem.first);
                num2freq.erase(elem.first);
                break;
            }
        }
    }
    return res;
}

//! 739.每日温度
vector<int> dailyTemperatures(vector<int>& temperatures) {
    std::stack<int> st;
    vector<int> res(temperatures.size(), 0);
    st.push(0);
    for(int i=1; i<temperatures.size(); i++) {
        if(!st.empty() && temperatures[i] > temperatures[st.top()]) {
            while(!st.empty() && temperatures[i] > temperatures[st.top()]) {
                res[st.top()] = i - st.top();
                st.pop();
            }
        }
        st.push(i);
    }
    return res;
}

//! 496. 下一个更大元素 I
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    map<int,int> m_nums2;
    std::stack<int> st;
    vector<int> res(nums1.size(), -1);
    st.push(0);
    m_nums2[nums2[0]] = -1;
    for (int i=1; i< nums2.size(); i++) {
        if(!st.empty() && nums2[i] > nums2[st.top()]) {
            while(!st.empty() && nums2[i] > nums2[st.top()]) {
                m_nums2[nums2[st.top()]] = nums2[i];
                st.pop();
            }
        }
        st.push(i);
        m_nums2[nums2[i]] = -1;
    }

    for (int i=0; i< nums1.size(); i++) {
        res[i] = m_nums2[nums1[i]];
    }

    return res;
}

//! 503. 下一个更大元素 II
vector<int> nextGreaterElements(vector<int>& nums) {
    std::stack<int> st;
    vector<int> res(nums.size(), -1);
    st.push(0);
    int n = nums.size();
    for (int i=1; i< n; i++) {
        if(!st.empty() && nums[i] > nums[st.top()]) {
            while(!st.empty() && nums[i] > nums[st.top()]) {
                res[st.top()] = nums[i];
                st.pop();
            }
        }
        st.push(i);
    }

    for (int i=0; i< n; i++) {
        if(!st.empty() && nums[i] > nums[st.top()]) {
            while(!st.empty() && nums[i] > nums[st.top()]) {
                res[st.top()] = nums[i];
                st.pop();
            }
        }
    }

    return res;
}

//! 42.接雨水
int trap(vector<int>& height) {

}
